package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/30 14:25
 **/
public class Day45_6_Offer12_Exist {
    class Solution {
        public boolean exist(char[][] board, String word) {
            for(int i = 0; i < board.length; ++i){
                for(int j = 0; j < board[0].length; ++j){
                    if(board[i][j] == word.charAt(0)){
                        if(findWord(board, word, i, j, 0)){
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        private boolean findWord(char[][] board, String word, int i, int j, int k){
            if(k >= word.length()) return true;
            if(i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
                    board[i][j] != word.charAt(k)) return false;

            board[i][j] += 58;
            boolean res = findWord(board, word, i+1, j, k+1) || findWord(board, word, i-1, j, k+1) ||
                    findWord(board, word, i, j+1, k+1) || findWord(board, word, i, j-1, k+1);
            board[i][j] -= 58;
            return res;
        }
    }
}